package com.example.leetcode.trainingcamp.week5.Sunday;

import java.util.HashSet;
import java.util.Set;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 *
 * <p>图示两个链表在节点 c1 开始相交：
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test150 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode preA = headA;
       ListNode preB = headB;
       Set<ListNode> set = new HashSet<>();
       while (preA != null){
           set.add(preA);
           preA = preA.next;
       }
       while (preB != null){
           if (set.contains(preB)){
               return preB;
           }
           preB = preB.next;
       }
       return null;
    }
}
